package com.kznnc.data_structure.sort.one;

/**
 * @Description
 *  1. 将所有要排序的数字,划分为有序序列, 和无序序列
 *  2. 有序序列可以从一个开始, 将无序的数字, 插入到有序序列中应该存放的位置
 *  3. 将无序序列, 插入到有序序列,插入完毕, (重复2步骤)
 * @Author houchenkai
 * @Created Date: 2021/6/24 19:47
 * @ClassName
 */
public class InsertionSortDemo {


    public static void main(String[] args) {
        int[] arr = {9,8,7,10,1,3,2};
        bigToSmallSort(arr);
      //  smallToBigSort(arr);
    }
// [0] [1] [2] [3] || [4]  [5]
    public static void bigToSmallSort(int [] arr) {

        int allNum = arr.length-1;
        for (int i =allNum-1 ; i >=0  ; i--) {
              int data = arr[i];
              int j = i+1;
            for (; j <= allNum; j++) {
                if (arr[j] > data ){
                    arr[j-1] =arr[j];
                  //  arr[j] =data;  =    arr[j-1] =data;
                }else {
                    //  arr[j-1] =data; 不能放到这的原因是 比我小的时候 就已经结束了
                    break;
                }
            }
            arr[j-1] =data;
        }
        for (int i : arr) {
            System.out.println(i);
        }


    }





    public static void smallToBigSort(int [] arr) {

        // 从第二个开始作为 待排序的分组
        for (int i = 1; i < arr.length; i++) {
            int data = arr[i];

            // 和排序好的数字一一比较, 比当前未排好序的 比较
            // 比我大就 给我让地方  我认为这块就可能是 我的地方了
            // 再往前走一个发现比我小 就知道后面那个是我的位置
            int j = i-1;
            for (; j >=0; j--) {
                // 比我大就 给我让地方  我认为这块就可能是 我的地方了
                if (data< arr[j]) {
                    arr[j+1] =arr[j];
                }else {
                    //   arr[j+1] = data; 不能放这的原因是
                    // 再往前走一个发现比我小 就知道后面那个是我的位置
                    break;
                }
            }
            // 再往前走一个发现比我小 就知道后面那个是我的位置
            arr[j+1] = data;
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
